#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Node for linked list or binary tree. */
typedef struct Node {
	char *filename;
	struct Node *left;
	struct Node *right;
} Node;

/* Function declarations. */
char** getSampleData();
Node* makeTree(char **array);
Node* makeTree2(int low, int high, char **array);
void add(Node *root, char data[]);
void delete(Node *node, char data[]);
void deleteRandom(Node *root);
Node* search(Node *node, char *value);
Node* findLeftmost(Node *node);
Node* findRightmost(Node *node);
Node* getPreorder(Node *node);
void getPreorder2(Node *node, Node *list);
Node* getInorder(Node *node);
void getInorder2(Node *node, Node *listhead);
Node* getPostorder(Node *node);
void getPostorder2(Node *node, Node *listhead);
void printPreorder(Node *root);
void printInorder(Node *root);
void printPostorder(Node *root);
int getDepth(Node *node);
void freeArray(char **array);
void freeLinkedList(Node *listhead);
void freeTree(Node *root);

/* 2D array size for testing. */
int numStrings = 10;
int stringLength = 10;

/**
 * Main function to test the program.
 * @return	0 on success.
 */
int main() {
	printf("\n");

	// Seed time
	srand(time(NULL));
	
	// Create an input array with sample data for testing
	char **array = getSampleData();
	
	// Create binary search tree from array
	Node *root = makeTree(array);
	
	// Test delete function
	char testdelete[5] = "4";
	delete(root, testdelete);
	
	// Test add function
	char testadd[5] = "4";
	add(root, testadd);
	
	// Test search function
	char testsearch[5] = "9";
	Node *result = search(root, testsearch);
	if (result != NULL) {
		printf("Node with value %s found\n", result->filename);
	}
	
	// Test random delete function
	deleteRandom(root);
	
	// Test tree traversal functions
	printPreorder(root);
	printInorder(root);
	printPostorder(root);
	
	// Test tree depth function
	int depth = getDepth(root);
	printf("Tree depth: %d\n", depth);
	
	freeArray(array);
	freeTree(root);
	
	printf("\n");
	return(0);
}

/**
 * Preload elements in 2D array with data.
 * @return	Pointer to an array of data.
 */
char** getSampleData() {
	// Create first dimension of array
	char **array = (char **) malloc(numStrings * sizeof(*array));
	// Create second dimension of array
	for (int i = 0; i < numStrings; i++) {
		array[i] = (char *) malloc(stringLength * sizeof(char));
	}
	for (int i = 0; i < numStrings; i++) {
		// Fill array with sample numbers as strings
		sprintf(array[i], "%d", i);
	}
	return array;
}

/**
 * Create binary search tree from array.
 * @param		2D array of character strings.
 * @return	Pointer to the root of the tree.
 */
Node* makeTree(char **array) {
	int low = 0;
	int high = numStrings - 1;
	return makeTree2(low, high, array);
}

/**
 * Create binary search tree from array.
 * @param		low The lowest array position.
 * @param		high The highest array position.
 * @param		2D array of character strings.
 * @return	Pointer to the root of the tree.
 */
Node* makeTree2(int low, int high, char **array) {
	if (low > high) {
		return NULL;
	}
	else {
		int mid = (low + high) / 2;
		Node *node = (Node *) malloc(sizeof(Node));
		node->filename = (char *) malloc(sizeof(array[mid]));		
		strcpy(node->filename, array[mid]);
		node->left = makeTree2(low, (mid - 1), array);
		node->right = makeTree2((mid + 1), high, array);
		return node;
	}
}

/**
 * Add a new node to the tree.
 * @param root The root node.
 * @param data The data in the new node to add.
 */
void add(Node *root, char data[]) {
	Node *node = root;
	Node *leaf = root;
	// Recurse down the tree until we reach the leaf node
	while (leaf != NULL) {
		node = leaf;
		if (strcmp(data, leaf->filename) < 0) {
			leaf = leaf->left;
		}
		else {
			leaf = leaf->right;
		}
	}
	// Create a new node
	Node *newNode = (Node *) malloc(sizeof(Node));
	newNode->filename = (char *) malloc(sizeof(data));
	strcpy(newNode->filename, data);
	newNode->left = 0;
	newNode->right = 0;
	// Attach the new node to the tree
	if (strcmp(data, node->filename) <= 0) {
		node->left = newNode;
	}
	else {
		node->right = newNode;
	}
}

/**
 * Delete a node from the tree with the matching data.
 * @param node The root node.
 * @param value The node with the matching value.
 */
void delete(Node *node, char value[]) {
	// Empty tree
	if (node == NULL) {
		return;
	}
	Node *x = node;
	Node *y = node;
	int match = 1;
	
	// Do binary search and look for a match
	while (strcmp(value, x->filename) != 0 && match == 1) {
		y = x;
		if (strcmp(value, x->filename) < 0 && x->left != NULL) {
			x = x->left;
		}
		else if (strcmp(value, x->filename) > 0 && x->right != NULL) {
			x = x->right;
		}
		else {
			// No match
			match = 0;
		}
	}
	
	if (match == 1) {
		// Case 0: Node to be removed is also the root
		if (node->left == NULL && node->right == NULL) {
			return;
		}
		// Case 1: Node to be removed is a leaf but not a root
		else if (x->left == NULL && x->right == NULL) {
			// Remove the leaf from the tree
			if (y->left == x) {
				y->left = x->left;
				free(x->filename);
				free(x);
			}
			else if (y->right == x) {
				y->right = x->right;
				free(x->filename);
				free(x);
			}
		}
		// Case 2: Only right subtree exists
		else if (x->left == NULL && x->right != NULL) {
			// Find leftmost child node in the right subtree
			Node *leftmost = findLeftmost(x);
			strcpy(x->filename, leftmost->filename);
			free(leftmost->filename);
			free(leftmost);
		}
		// Case 3: Only left subtree exists
		else if (x->left != NULL && x->right == NULL) {
			// Find rightmost child node in left subtree
			Node *rightmost = findRightmost(x);
			strcpy(x->filename, rightmost->filename);
			free(rightmost->filename);
			free(rightmost);
		}
		// Case 4: Both subtrees exist
		else {
			// Randomly go left or right
			int num = rand() % 2;
			if (num == 0) {
				// Find rightmost child node in left subtree
				Node *rightmost = findRightmost(x);
				strcpy(x->filename, rightmost->filename);
				free(rightmost->filename);
				free(rightmost);
			}
			else {
				// Find leftmost child node in right subtree
				Node *leftmost = findLeftmost(x);
				strcpy(x->filename, leftmost->filename);
				free(leftmost->filename);
				free(leftmost);
			}
		}
	}
	else {
		printf("Unable to remove node because it does not exist.\n");
	}
}

/**
 * Remove a percentage of elements randomly from the tree.
 * @param root The root of the tree.
 */
void deleteRandom(Node *root) {
	// Get the elements from the tree in order
	Node *list = getInorder(root);
	Node *temp = list;
	int count = 0;
	// Get the count of elements in the list
	while (temp != NULL) {
		count++;
		temp = temp->right;
	}
	// Get the number of elements to remove, max is count - 1
	int numToRemove = rand() % (count);
	printf("Removing %d elements\n", numToRemove);
	for (int i = 0; i < numToRemove; i++) {
		// Remove a random element
		int elementPosition = rand() % count;
		Node *position = list;
		Node *prevPos = list;
		for (int j = 0; j < elementPosition; j++) {
			prevPos = position;
			position = position->right;
		}
		// Case 1: Delete the head node in the list
		if (elementPosition == 0) {
			//printf("Position 0 is %s\n", position->filename);
			list = list->right;
			printf("Removing %s\n", position->filename);
			delete(root, position->filename);
			free(position->filename);
			free(position);
			count--;
		}
		// Case 2: Delete a non-head node in the list
		else {
			prevPos->right = position->right;
			printf("Removing %s\n", position->filename);
			delete(root, position->filename);
			free(position->filename);
			free(position);
			count--;
		}
	}
	freeLinkedList(list);
}

/**
 * Binary search for a node in the tree.
 * @param node The root of the tree.
 * @param value The value of the node to search for.
 * @return The node with the matching value.
 */
Node* search(Node *node, char *value) {
	// Base case 1, empty tree or node not found
	if (node == NULL) {
		printf("Unable to find node because it does not exist.\n");
	}
	// Base case 2, node found
	else if (strcmp(value, node->filename) == 0) {
		return node;
	}
	// If value is less than current node, go left
	else if (strcmp(value, node->filename) < 0) {
		return search(node->left, value);
	}
	// If value is greater than current node, go right
	else if (strcmp(value, node->filename) > 0) {
		return search(node->right, value);
	}
	return NULL;
}

/**
 * Replace the node to-be-deleted's value with the value of leftmost node in
 * the right subtree. Then delete this leftmost node.
 * @param node The node to-be-deleted.
 * @return The value of the leftmost node in the right subtree.
 */
Node* findLeftmost(Node *node) {
	Node *x = node->right;
	Node *y = node;
	Node *leftmost = 0;
	
	// Keep going left down the tree until we hit the leftmost node
	while (x->left != NULL) {
		y = x;
		x = x-> left;
	}
	// Save the leftmost node
	leftmost = x;
	
	// Case 0: The leftmost node is a leaf.  Delete it.
	if (x->right == NULL) {
		if (y->right == x) {
			y->right = x-> right;
		}
		else {
			y->left = x->left;
		}
	}
	// Case 1: The leftmost node has a right subtree. Delete it.
	// Note: It is not possible for the leftmost node to have a left subtree.
	else if (x->right != NULL) {
		if (y->right == x) {
			y->right = x->right;
		}
		else {
			y->left = x->right;
		}
	}
	return leftmost;
}

/**
 * Replace the node to-be-deleted's value with the value of rightmost node in
 * the left subtree. Then delete this rightmost node.
 * @param node The node to-be-deleted.
 * @return The value of the rightmost node in the left subtree.
 */
Node* findRightmost(Node *node) {
	Node *x = node->left;
	Node *y = node;
	Node *rightmost = 0;
	
	// Keep going right down the tree until we hit the rightmost node
	while (x->right != NULL) {
		y = x;
		x = x->right;
	}
	// Save the rightmost node
	rightmost = x;
	
	// Case 0: The rightmost node is a leaf.  Delete it.
	if (x->left == NULL) {
		if (y->left == x) {
			y->left = x->left;
		}
		else {
			y->right = x->right;
		}
	}
	// Case 1: The rightmost node has a left subtree. Delete it.
	// Note: It is not possible for the rightmost node to have a right subtree.
	else if (x->left != NULL) {
		if (y->left == x) {
			y->left = x->left;
		}
		else {
			y->right = x->left;
		}
	}
	return rightmost;
}

/**
 * Traverse the tree in preorder.
 * @param node The root of the tree.
 * @return Linked list containing the elements in preorder.
 */ 
Node* getPreorder(Node *node) {
	Node *listhead = (Node *) malloc(sizeof(Node));
	listhead->right = 0;
	getPreorder2(node, listhead);
	// Remove the first node which contains nothing
	Node *first = listhead;
	listhead = listhead->right;
	free(first);
	return listhead;
}

/**
 * Traverse the tree in preorder and place them into linked list.
 * @param		node The root of the tree.
 * @param		listhead The head of the linked list.
 */
void getPreorder2(Node *node, Node *listhead) {
	Node *temp = listhead;
	if (node != NULL) {
		// Traverse to the end of the linked list
		while (temp->right != NULL) {
			temp = temp->right;
		}
		temp->right = (Node *) malloc(sizeof(Node));
		temp = temp->right;
		temp->filename = (char *) malloc(sizeof(node->filename));
		strcpy(temp->filename, node->filename);
		temp->right = 0;
		getPreorder2(node->left, listhead);
		getPreorder2(node->right, listhead);
	}
}

/**
 * Traverse the tree in order.
 * @param node The root of the tree.
 * @return Linked list containing the elements in order.
 */ 
Node* getInorder(Node *node) {
	Node *listhead = (Node *) malloc(sizeof(Node));
	listhead->right = 0;
	getInorder2(node, listhead);
	// Remove the first node which contains nothing
	Node *first = listhead;
	listhead = listhead->right;
	free(first);
	return listhead;
}

/**
 * Traverse the tree in order and place them into linked list.
 * @param		node The root of the tree.
 * @param		listhead The head of the linked list.
 */
void getInorder2(Node *node, Node *listhead) {	
	if (node == NULL) {
		return;
	}
	if (node->left != NULL) {
		getInorder2(node->left, listhead);
	}
	Node *temp = listhead;
	// Traverse to the end of the linked list
	while (temp->right != NULL) {
		temp = temp->right;
	}
	temp->right = (Node *) malloc(sizeof(Node));
	temp = temp->right;
	temp->filename = (char *) malloc(sizeof(node->filename));
	strcpy(temp->filename, node->filename);
	temp->right = 0;
	if (node->right != NULL) {
		getInorder2(node->right, listhead);
	}
}

/**
 * Traverse the tree in postorder.
 * @param node The root of the tree.
 * @return Linked list containing the elements in postorder.
 */ 
Node* getPostorder(Node *node) {
	Node *listhead = (Node *) malloc(sizeof(Node));
	listhead->right = 0;
	getPostorder2(node, listhead);
	// Remove the first node which contains nothing
	Node *first = listhead;
	listhead = listhead->right;
	free(first);
	return listhead;
}

/**
 * Traverse the tree in postorder and place them into linked list.
 * @param		node The root of the tree.
 * @param		listhead The head of the linked list.
 */
void getPostorder2(Node *node, Node *listhead) {	
	if (node == NULL) {
		return;
	}
	if (node->left != NULL) {
		getPostorder2(node->left, listhead);
	}
	if (node->right != NULL) {
		getPostorder2(node->right, listhead);
	}
	Node *temp = listhead;
	// Traverse to the end of the linked list
	while (temp->right != NULL) {
		temp = temp->right;
	}
	temp->right = (Node *) malloc(sizeof(Node));
	temp = temp->right;
	temp->filename = (char *) malloc(sizeof(node->filename));
	strcpy(temp->filename, node->filename);
	temp->right = 0;
}

/**
 * Get the tree depth.
 * @param node The root of the tree.
 * @return The number of levels in the tree.
 */
int getDepth(Node *node) {
	if (node == NULL) {
		return 0;
	}
	int level = 1;
	level += max(getDepth(node->left), getDepth(node->right));
	return level;
}

/**
 * Get the max of two integers.
 * @param		a The first integer.
 * @param		b The first integer.
 * @return	The max of a and b.
 */
int max(int a, int b) {
    if (a > b) return a;
    else return b;
}

/**
 * Print the value of the elements in the tree using preorder traversal.
 * @param		root The root of the tree.
 */
void printPreorder(Node *root) {
	Node *list = getPreorder(root);
	Node *temp = list;
	printf("Preorder:\t");
	while (temp != NULL) {
		printf("%s ", temp->filename);
		temp = temp->right;
	}
	printf("\n");
	freeLinkedList(list);
}

/**
 * Print the value of the elements in the tree using inorder traversal.
 * @param		root The root of the tree.
 */
void printInorder(Node *root) {
	Node *list = getInorder(root);
	Node *temp = list;
	printf("Inorder:\t");
	while (temp != NULL) {
		printf("%s ", temp->filename);
		temp = temp->right;
	}
	printf("\n");
	freeLinkedList(list);
}

/**
 * Print the value of the elements in the tree using postorder traversal.
 * @param		root The root of the tree.
 */
void printPostorder(Node *root) {
	Node *list = getPostorder(root);
	Node *temp = list;
	printf("Postorder:\t");
	while (temp != NULL) {
		printf("%s ", temp->filename);
		temp = temp->right;
	}
	printf("\n");
	freeLinkedList(list);
}

/**
 * Free dynamically allocated memory in 2D array.
 * @param		2D array.
 */
void freeArray(char **array) {
	for (int i = 0; i < numStrings; i++) {
		//printf("free %s\n", array[i]);
		free(array[i]);
	}
	free(array);
}

/**
 * Free dynamically allocated memory in linked list.
 * @param		listhead The head of the linked list.
 */
void freeLinkedList(Node *listhead) {
	while (listhead != NULL) {
		Node *temp = listhead;
		listhead = listhead->right;
		//printf("free %s\n", temp->filename);
		free(temp->filename);
		free(temp);
	}
}

/**
 * Free dynamically allocated memory in nodes under the given node.
 * @param		node The root node of the tree to free.
 */
void freeTree(Node *node) {
	if (node != NULL) {
		freeTree(node->left);
		freeTree(node->right);
		//printf("free %s\n", node->filename);
		free(node->filename);
		free(node);
	}
}
